package sortStudy;

import java.util.Random;

public class FindKthLargest {

    private static Random random = new Random();

    /**
     * LeetCode T215 数组中的第K个最大元素
     *
     * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
     *
     * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
     *
     * 总结：如何使得递归在中间
     * @param args
     */
    public static void main(String[] args) {

    }

    //方法一：使用快排
    public int findKthLargest(int[] nums, int k) {
        return selectQuick(nums, 0, nums.length - 1, nums.length - k);
    }

    public int selectQuick(int[] nums, int left, int right, int index){
        //进行一次排序，获得下标
        int i = partition(nums, left, right);
        //设置出口
        if (i == index){
            return nums[i];
        }
        return i > index?selectQuick(nums, left, i - 1, index):selectQuick(nums, i+1, right, index);
    }

    public int partition(int[] nums, int left, int right){
        //确定坐标
        int index = random.nextInt(right - left + 1) + left;
        swap(nums, index, right);
        int key = nums[right];
        int i = left - 1;
        for (int j = left; j < right; j++){
            if (nums[j] < key){
                swap(nums, ++i, j);
            }
        }
        swap(nums, i + 1, right);
        return i + 1;
    }

    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    //方法二：使用堆排序
}
